package com.dong.ch08_heap;

import java.util.Comparator;

/**
 * 优先队列, 0号元素空出, 最大堆
 * @param <E>
 */
public class MaxHeap<E extends Comparable<E>> implements Queue<E>{
    E[] array=null;
    //因为0号元素不使用, 初始size=1, 方便统一操作,
    int size = 1;
    Comparator comparator =null;

    public MaxHeap(int size, Comparator comparator) {
        this.array = (E[]) new Object[size];
        this.comparator=comparator;
    }
    public MaxHeap(Comparator comparator) {
        this(8,comparator);
    }
    public MaxHeap() {
        this(8,null);
    }

    private boolean hasChild(int index) {
        return index*2+1<=size;
    }
    private boolean hasRightChile(int index) {
        return index*2+1<=size;
    }
    private int getParent(int index) {
        if(!hasParent(index)){
            throw new RuntimeException("reach the root already!");
        }
        return index/2;
    }
    public boolean hasParent(int index) {
        return index>1;
    }
    boolean validateExistIndex(int index) {
        return index<=size&&index>=1;
    }
    private void swapArr(int index1,int index2) {
        if(validateExistIndex(index1)&&validateExistIndex(index2)) {
            E tmp = array[index1];
            array[index1]=array[index2];
            array[index2]=tmp;
        }else {
            throw new RuntimeException("index out of range!");
        }

    }

    private void siftUp(int index) {
        E current = array[index];
        int tmpIndex = index;
        while(compareElementIndex(tmpIndex,tmpIndex/2)>0&&hasParent(tmpIndex)) {
            int parentIndex = getParent(tmpIndex);
            swapArr(parentIndex,tmpIndex);
            tmpIndex=parentIndex;
        }

    }
    private int getMaxChild(int index) {
        if(!hasChild(index)) {
            throw new IllegalArgumentException("index of of range");
        }else {
            if(index*2==size) {
                return index*2;
            }
            int compareResult = compareElementIndex(index * 2, index * 2 + 1);
            return compareResult>0?index*2:index*2+1;
        }
    }

    /**
     * 返回左右两个索引的元素比较结果
     * @param left
     * @param right
     * @return
     */
    private int compareElementIndex(int left ,int right) {
        if(comparator==null) {
            return array[left].compareTo(array[right]);
        }else {
            return comparator.compare(array[left], array[right]);
        }
    }
    private void siftDown() {
        E current = array[1];
        int tmpIndex = 1;
        int maxChild = getMaxChild(tmpIndex);
        while(compareElementIndex(tmpIndex,maxChild)<0&&hasChild(tmpIndex)) {
            swapArr(tmpIndex,maxChild);
            tmpIndex=maxChild;
            maxChild=getMaxChild(tmpIndex);
        }
    }


    public void resize(boolean doubleSize) {
        if(doubleSize) {
            E[] newArray = (E[]) new Object[array.length*2];
            System.arraycopy(array,0,newArray,0,size);
            array=newArray;
        }else {
            E[] newArray = (E[]) new Object[array.length/2];
            System.arraycopy(array,0,newArray,0,size);
            array=newArray;
        }
    }

    @Override
    public int getSize() {
        return size-1;
    }

    @Override
    public boolean isEmpty() {
        return getSize()==0;
    }

    @Override
    public void enqueue(E e) {
        if(size>=array.length) {
            //扩容
          resize(true);
        }
        array[size++]=e;
        siftUp(size);
    }


    @Override
    public E dequeue() {
        if(size*4<=array.length) {
           resize(false);
        }
        if(isEmpty()) {
            throw new RuntimeException("the queue is empty now !");
        }
        E current = array[1];
        array[1]=array[size];
        array[size]=null;
        size--;
        siftDown();
        return current;
    }

    @Override
    public E getFront() {
        return array[1];
    }
}
